// 数组中的第K个最大元素

package Leetcode;

import java.util.Random;

class Solution_215 {
    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k, 0, nums.length - 1);
    }

    // 快速选择算法，(数组，目标值，最左边界，最右边界)
    public int quickSelect(int[] nums, int k, int left, int right) {
        // 随机选取一个元素作为枢轴元素
        int index = random.nextInt(right - left + 1) + left;
        // 保存目标值
        int target = nums[index];
        // 在进行第一次交换时，会丢失nums[left],因此需要保存
        nums[index] = nums[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] <= target)
                j--;
            nums[i] = nums[j];
            while (i < j && nums[i] >= target)
                i++;
            nums[j] = nums[i];
        }
        nums[i] = target;
        // 经过交换后，i左部均大于nums[i],右部均小于nums[i]
        if (i == k - 1)
            return nums[i];
        // 说明在左部分
        else if (i > k - 1)
            return quickSelect(nums, k, left, i - 1);
        else
            return quickSelect(nums, k, i + 1, right);
    }
}